#if !BESTHTTP_DISABLE_ALTERNATE_SSL && (!UNITY_WEBGL || UNITY_EDITOR)
#pragma warning disable
using System;
using BestHTTP.SecureProtocol.Org.BouncyCastle.Crypto;
using BestHTTP.SecureProtocol.Org.BouncyCastle.Security;
using BestHTTP.SecureProtocol.Org.BouncyCastle.Utilities;
namespace BestHTTP.SecureProtocol.Org.BouncyCastle.Math
{
/**
* Utility methods for generating primes and testing for primality.
*/
public abstract class Primes
{
public static readonly int SmallFactorLimit = 211;
private static readonly BigInteger One = BigInteger.One;
private static readonly BigInteger Two = BigInteger.Two;
private static readonly BigInteger Three = BigInteger.Three;
/**
* Used to return the output from the
* {@linkplain Primes#enhancedMRProbablePrimeTest(BigInteger, SecureRandom, int) Enhanced
* Miller-Rabin Probabilistic Primality Test}
*/
public class MROutput
{
internal static MROutput ProbablyPrime()
{
return new MROutput(false, null);
}
internal static MROutput ProvablyCompositeWithFactor(BigInteger factor)
{
return new MROutput(true, factor);
}
internal static MROutput ProvablyCompositeNotPrimePower()
{
return new MROutput(true, null);
}
private readonly bool mProvablyComposite;
private readonly BigInteger mFactor;
private MROutput(bool provablyComposite, BigInteger factor)
{
this.mProvablyComposite = provablyComposite;
this.mFactor = factor;
}
public BigInteger Factor
{
get { return mFactor; }
}
public bool IsProvablyComposite
{
get { return mProvablyComposite; }
}
public bool IsNotPrimePower
{
get { return mProvablyComposite && mFactor == null; }
}
}
/**
* Used to return the output from the {@linkplain Primes#generateSTRandomPrime(Digest, int, byte[]) Shawe-Taylor Random_Prime Routine}
*/
public class STOutput
{
private readonly BigInteger mPrime;
private readonly byte[] mPrimeSeed;
private readonly int mPrimeGenCounter;
internal STOutput(BigInteger prime, byte[] primeSeed, int primeGenCounter)
{
this.mPrime = prime;
this.mPrimeSeed = primeSeed;
this.mPrimeGenCounter = primeGenCounter;
}
public BigInteger Prime
{
get { return mPrime; }
}
public byte[] PrimeSeed
{
get { return mPrimeSeed; }
}
public int PrimeGenCounter
{
get { return mPrimeGenCounter; }
}
}
/**
* FIPS 186-4 C.6 Shawe-Taylor Random_Prime Routine
*
* Construct a provable prime number using a hash function.
*
* @param hash
* the {@link Digest} instance to use (as "Hash()"). Cannot be null.
* @param length
* the length (in bits) of the prime to be generated. Must be at least 2.
* @param inputSeed
* the seed to be used for the generation of the requested prime. Cannot be null or
* empty.
* @return an {@link STOutput} instance containing the requested prime.
*/
public static STOutput GenerateSTRandomPrime(IDigest hash, int length, byte[] inputSeed)
{
if (hash == null)
throw new ArgumentNullException("hash");
if (length < 2)
throw new ArgumentException("must be >= 2", "length");
if (inputSeed == null)
throw new ArgumentNullException("inputSeed");
if (inputSeed.Length == 0)
throw new ArgumentException("cannot be empty", "inputSeed");
return ImplSTRandomPrime(hash, length, Arrays.Clone(inputSeed));
}
/**
* FIPS 186-4 C.3.2 Enhanced Miller-Rabin Probabilistic Primality Test
*
* Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases. This is an
* alternative to {@link #isMRProbablePrime(BigInteger, SecureRandom, int)} that provides more
* information about a composite candidate, which may be useful when generating or validating
* RSA moduli.
*
* @param candidate
* the {@link BigInteger} instance to test for primality.
* @param random
* the source of randomness to use to choose bases.
* @param iterations
* the number of randomly-chosen bases to perform the test for.
* @return an {@link MROutput} instance that can be further queried for details.
*/
public static MROutput EnhancedMRProbablePrimeTest(BigInteger candidate, SecureRandom random, int iterations)
{
CheckCandidate(candidate, "candidate");
if (random == null)
throw new ArgumentNullException("random");
if (iterations < 1)
throw new ArgumentException("must be > 0", "iterations");
if (candidate.BitLength == 2)
return MROutput.ProbablyPrime();
if (!candidate.TestBit(0))
return MROutput.ProvablyCompositeWithFactor(Two);
BigInteger w = candidate;
BigInteger wSubOne = candidate.Subtract(One);
BigInteger wSubTwo = candidate.Subtract(Two);
int a = wSubOne.GetLowestSetBit();
BigInteger m = wSubOne.ShiftRight(a);
for (int i = 0; i < iterations; ++i)
{
BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random);
BigInteger g = b.Gcd(w);
if (g.CompareTo(One) > 0)
return MROutput.ProvablyCompositeWithFactor(g);
BigInteger z = b.ModPow(m, w);
if (z.Equals(One) || z.Equals(wSubOne))
continue;
bool primeToBase = false;
BigInteger x = z;
for (int j = 1; j < a; ++j)
{
z = z.ModPow(Two, w);
if (z.Equals(wSubOne))
{
primeToBase = true;
break;
}
if (z.Equals(One))
break;
x = z;
}
if (!primeToBase)
{
if (!z.Equals(One))
{
x = z;
z = z.ModPow(Two, w);
if (!z.Equals(One))
{
x = z;
}
}
g = x.Subtract(One).Gcd(w);
if (g.CompareTo(One) > 0)
return MROutput.ProvablyCompositeWithFactor(g);
return MROutput.ProvablyCompositeNotPrimePower();
}
}
return MROutput.ProbablyPrime();
}
/**
* A fast check for small divisors, up to some implementation-specific limit.
*
* @param candidate
* the {@link BigInteger} instance to test for division by small factors.
*
* @return <code>true</code> if the candidate is found to have any small factors,
* <code>false</code> otherwise.
*/
public static bool HasAnySmallFactors(BigInteger candidate)
{
CheckCandidate(candidate, "candidate");
return ImplHasAnySmallFactors(candidate);
}
/**
* FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test
*
* Run several iterations of the Miller-Rabin algorithm with randomly-chosen bases.
*
* @param candidate
* the {@link BigInteger} instance to test for primality.
* @param random
* the source of randomness to use to choose bases.
* @param iterations
* the number of randomly-chosen bases to perform the test for.
* @return <code>false</code> if any witness to compositeness is found amongst the chosen bases
* (so <code>candidate</code> is definitely NOT prime), or else <code>true</code>
* (indicating primality with some probability dependent on the number of iterations
* that were performed).
*/
public static bool IsMRProbablePrime(BigInteger candidate, SecureRandom random, int iterations)
{
CheckCandidate(candidate, "candidate");
if (random == null)
throw new ArgumentException("cannot be null", "random");
if (iterations < 1)
throw new ArgumentException("must be > 0", "iterations");
if (candidate.BitLength == 2)
return true;
if (!candidate.TestBit(0))
return false;
BigInteger w = candidate;
BigInteger wSubOne = candidate.Subtract(One);
BigInteger wSubTwo = candidate.Subtract(Two);
int a = wSubOne.GetLowestSetBit();
BigInteger m = wSubOne.ShiftRight(a);
for (int i = 0; i < iterations; ++i)
{
BigInteger b = BigIntegers.CreateRandomInRange(Two, wSubTwo, random);
if (!ImplMRProbablePrimeToBase(w, wSubOne, m, a, b))
return false;
}
return true;
}
/**
* FIPS 186-4 C.3.1 Miller-Rabin Probabilistic Primality Test (to a fixed base).
*
* Run a single iteration of the Miller-Rabin algorithm against the specified base.
*
* @param candidate
* the {@link BigInteger} instance to test for primality.
* @param baseValue
* the base value to use for this iteration.
* @return <code>false</code> if the specified base is a witness to compositeness (so
* <code>candidate</code> is definitely NOT prime), or else <code>true</code>.
*/
public static bool IsMRProbablePrimeToBase(BigInteger candidate, BigInteger baseValue)
{
CheckCandidate(candidate, "candidate");
CheckCandidate(baseValue, "baseValue");
if (baseValue.CompareTo(candidate.Subtract(One)) >= 0)
throw new ArgumentException("must be < ('candidate' - 1)", "baseValue");
if (candidate.BitLength == 2)
return true;
BigInteger w = candidate;
BigInteger wSubOne = candidate.Subtract(One);
int a = wSubOne.GetLowestSetBit();
BigInteger m = wSubOne.ShiftRight(a);
return ImplMRProbablePrimeToBase(w, wSubOne, m, a, baseValue);
}
private static void CheckCandidate(BigInteger n, string name)
{
if (n == null || n.SignValue < 1 || n.BitLength < 2)
throw new ArgumentException("must be non-null and >= 2", name);
}
private static bool ImplHasAnySmallFactors(BigInteger x)
{
/*
* Bundle trial divisors into ~32-bit moduli then use fast tests on the ~32-bit remainders.
*/
int m = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23;
int r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 2) == 0 || (r % 3) == 0 || (r % 5) == 0 || (r % 7) == 0 || (r % 11) == 0 || (r % 13) == 0
|| (r % 17) == 0 || (r % 19) == 0 || (r % 23) == 0)
{
return true;
}
m = 29 * 31 * 37 * 41 * 43;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 29) == 0 || (r % 31) == 0 || (r % 37) == 0 || (r % 41) == 0 || (r % 43) == 0)
{
return true;
}
m = 47 * 53 * 59 * 61 * 67;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 47) == 0 || (r % 53) == 0 || (r % 59) == 0 || (r % 61) == 0 || (r % 67) == 0)
{
return true;
}
m = 71 * 73 * 79 * 83;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 71) == 0 || (r % 73) == 0 || (r % 79) == 0 || (r % 83) == 0)
{
return true;
}
m = 89 * 97 * 101 * 103;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 89) == 0 || (r % 97) == 0 || (r % 101) == 0 || (r % 103) == 0)
{
return true;
}
m = 107 * 109 * 113 * 127;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 107) == 0 || (r % 109) == 0 || (r % 113) == 0 || (r % 127) == 0)
{
return true;
}
m = 131 * 137 * 139 * 149;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 131) == 0 || (r % 137) == 0 || (r % 139) == 0 || (r % 149) == 0)
{
return true;
}
m = 151 * 157 * 163 * 167;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 151) == 0 || (r % 157) == 0 || (r % 163) == 0 || (r % 167) == 0)
{
return true;
}
m = 173 * 179 * 181 * 191;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 173) == 0 || (r % 179) == 0 || (r % 181) == 0 || (r % 191) == 0)
{
return true;
}
m = 193 * 197 * 199 * 211;
r = x.Mod(BigInteger.ValueOf(m)).IntValue;
if ((r % 193) == 0 || (r % 197) == 0 || (r % 199) == 0 || (r % 211) == 0)
{
return true;
}
/*
* NOTE: Unit tests depend on SMALL_FACTOR_LIMIT matching the
* highest small factor tested here.
*/
return false;
}
private static bool ImplMRProbablePrimeToBase(BigInteger w, BigInteger wSubOne, BigInteger m, int a, BigInteger b)
{
BigInteger z = b.ModPow(m, w);
if (z.Equals(One) || z.Equals(wSubOne))
return true;
bool result = false;
for (int j = 1; j < a; ++j)
{
z = z.ModPow(Two, w);
if (z.Equals(wSubOne))
{
result = true;
break;
}
if (z.Equals(One))
return false;
}
return result;
}
private static STOutput ImplSTRandomPrime(IDigest d, int length, byte[] primeSeed)
{
int dLen = d.GetDigestSize();
if (length < 33)
{
int primeGenCounter = 0;
byte[] c0 = new byte[dLen];
byte[] c1 = new byte[dLen];
for (;;)
{
Hash(d, primeSeed, c0, 0);
Inc(primeSeed, 1);
Hash(d, primeSeed, c1, 0);
Inc(primeSeed, 1);
uint c = Extract32(c0) ^ Extract32(c1);
c &= (uint.MaxValue >> (32 - length));
c |= (1U << (length - 1)) | 1U;
++primeGenCounter;
if (IsPrime32(c))
{
return new STOutput(BigInteger.ValueOf((long)c), primeSeed, primeGenCounter);
}
if (primeGenCounter > (4 * length))
{
throw new InvalidOperationException("Too many iterations in Shawe-Taylor Random_Prime Routine");
}
}
}
STOutput rec = ImplSTRandomPrime(d, (length + 3)/2, primeSeed);
{
BigInteger c0 = rec.Prime;
primeSeed = rec.PrimeSeed;
int primeGenCounter = rec.PrimeGenCounter;
int outlen = 8 * dLen;
int iterations = (length - 1)/outlen;
int oldCounter = primeGenCounter;
BigInteger x = HashGen(d, primeSeed, iterations + 1);
x = x.Mod(One.ShiftLeft(length - 1)).SetBit(length - 1);
BigInteger c0x2 = c0.ShiftLeft(1);
BigInteger tx2 = x.Subtract(One).Divide(c0x2).Add(One).ShiftLeft(1);
int dt = 0;
BigInteger c = tx2.Multiply(c0).Add(One);
/*
* TODO Since the candidate primes are generated by constant steps ('c0x2'),
* sieving could be used here in place of the 'HasAnySmallFactors' approach.
*/
for (;;)
{
if (c.BitLength > length)
{
tx2 = One.ShiftLeft(length - 1).Subtract(One).Divide(c0x2).Add(One).ShiftLeft(1);
c = tx2.Multiply(c0).Add(One);
}
++primeGenCounter;
/*
* This is an optimization of the original algorithm, using trial division to screen out
* many non-primes quickly.
*
* NOTE: 'primeSeed' is still incremented as if we performed the full check!
*/
if (!ImplHasAnySmallFactors(c))
{
BigInteger a = HashGen(d, primeSeed, iterations + 1);
a = a.Mod(c.Subtract(Three)).Add(Two);
tx2 = tx2.Add(BigInteger.ValueOf(dt));
dt = 0;
BigInteger z = a.ModPow(tx2, c);
if (c.Gcd(z.Subtract(One)).Equals(One) && z.ModPow(c0, c).Equals(One))
{
return new STOutput(c, primeSeed, primeGenCounter);
}
}
else
{
Inc(primeSeed, iterations + 1);
}
if (primeGenCounter >= ((4 * length) + oldCounter))
{
throw new InvalidOperationException("Too many iterations in Shawe-Taylor Random_Prime Routine");
}
dt += 2;
c = c.Add(c0x2);
}
}
}
private static uint Extract32(byte[] bs)
{
uint result = 0;
int count = System.Math.Min(4, bs.Length);
for (int i = 0; i < count; ++i)
{
uint b = bs[bs.Length - (i + 1)];
result |= (b << (8 * i));
}
return result;
}
private static void Hash(IDigest d, byte[] input, byte[] output, int outPos)
{
d.BlockUpdate(input, 0, input.Length);
d.DoFinal(output, outPos);
}
private static BigInteger HashGen(IDigest d, byte[] seed, int count)
{
int dLen = d.GetDigestSize();
int pos = count * dLen;
byte[] buf = new byte[pos];
for (int i = 0; i < count; ++i)
{
pos -= dLen;
Hash(d, seed, buf, pos);
Inc(seed, 1);
}
return new BigInteger(1, buf);
}
private static void Inc(byte[] seed, int c)
{
int pos = seed.Length;
while (c > 0 && --pos >= 0)
{
c += seed[pos];
seed[pos] = (byte)c;
c >>= 8;
}
}
private static bool IsPrime32(uint x)
{
/*
* Use wheel factorization with 2, 3, 5 to select trial divisors.
*/
if (x <= 5)
{
return x == 2 || x == 3 || x == 5;
}
if ((x & 1) == 0 || (x % 3) == 0 || (x % 5) == 0)
{
return false;
}
uint[] ds = new uint[]{ 1, 7, 11, 13, 17, 19, 23, 29 };
uint b = 0;
for (int pos = 1; ; pos = 0)
{
/*
* Trial division by wheel-selected divisors
*/
while (pos < ds.Length)
{
uint d = b + ds[pos];
if (x % d == 0)
{
return x < 30;
}
++pos;
}
b += 30;
if ((b >> 16 != 0) || (b * b >= x))
{
return true;
}
}
}
}
}
#pragma warning restore
#endif
